public class TreeMap {
    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node(int val) {
            this.val = val;
        }
    }

    public Node root;
    /**
     * 查找
     * @param val
     * @return
     */
    public boolean selectVal(int val) {
        Node cur = root;
        if(null == root) {
            return false;
        }
        while(cur != null) {
             if(cur.val > val) {
                 cur = cur.right;
             }else if(cur.val < val) {
                 cur = cur.left;
             }else {
                 return true;
             }
        }
        return false;
    }

    /**
     * 插入元素
     * @param val
     */
    public void insert(int val) {
        Node node = new Node(val);
        if(root == null) {
            root = node;
            return;
        }
        Node cur = root;
        Node parent = null;
        while(cur != null) {
            parent = cur;
            if(cur.val > val) {
                cur = cur.left;
            }else if(cur.val < val) {
                cur = cur.right;
            }else {
                return;
            }
        }
        if(parent.val < val) {
            parent.right = node;
        }else {
            parent.left = node;
        }
    }

    /**
     * 删除元素
     * @param val
     *      1.找到该元素
     *      2.判断待删元素情况
     *      3.该元素左侧为空 在为前一个节点左-> 为前节点右
     *      4.该元素右侧为空 在为前一个节点左-> 为前节点右
     *      5.均不为空 替删,找到左子树最小值,进行交换,
     */
    public void remove(int val) {
        if(root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while(cur != null) {
            if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else {
                if(cur.left == null) {
                    if(root == cur) {
                        root = root.right;
                    }else if(parent.left == cur) {
                        parent.left = cur.right;
                    }else {
                        parent.right = cur.right;
                    }
                }else if(root.right == null) {
                    if(root == cur) {
                        root = root.left;
                    }else if(parent.left == cur) {
                        parent.left = cur.left;
                    }else {
                        parent.right = cur.left;
                    }
                }else {//右子树的最大值
                    Node t = cur.right;
                    Node tp = cur;
                    while(t.left != null) {
                        tp = t;
                        t = t.left;
                    }
                    cur.val = t.val;
                    if(tp.left == t) {
                        tp.left = t.right;
                    }else {
                        tp.right = t.right;
                    }
                }
            }
        }

    }
}
